home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
HULL.ARJ
/
HULL.C
next >
Wrap
C/C++ Source or Header
|
1992-07-15
|
4KB
|
155 lines
/* Copyright (c) 1992, by John Johnson
If you find this code useful, interesting or inspiring, I would
like to hear from you, contact me on D.W.'s Toolbox (404) 471-6636
Compiled using QuickC v2.5.
The following code was written based on algorithms in the book
'Algorithms' by Robert Sedgewick.
*/
#include <math.h>
#include <graph.h>
#include <float.h>
#include <stdlib.h>
struct POINT
{ float x;
float y;
};
//
// Passed two POINTs, returns a number between 0 and 360 that is
// NOT the angle made by p1 & p2 with the horizontal but which
// has the same order properties as that angle.
//
float theta(struct POINT p1, struct POINT p2)
{ float dx, dy, ax, ay;
float t;
dx = p2.x - p1.x; ax = fabs(dx);
dy = p2.y - p1.y; ay = fabs(dy);
if (dx == 0 && dy == 0)
t = 0;
else
t = dy / (ax + ay);
if (dx < 0)
t = 2 - t;
else
if (dy < 0)
t = 4 + t;
return t * 90.0;
}
//
// Function wrap taken from `Algorithms' pg. 364
//
// Given a set of POINTs, orders the points to produce
// a convex hull about the points. The first n points in the
// array are rearranged to generate this hull,
// and the number of points (n) on the hull is returned.
//
int wrap(struct POINT p[], int N)
{ int i, min, M;
float minangle, v;
struct POINT t;
min = 0;
for(i = 1; i < N; i++)
if (p[i].y < p[min].y) min = i;
M = -1;
p[N] = p[min];
minangle = 0.0;
do
{ M++;
t = p[M];
p[M] = p[min];
p[min] = t;
min = N;
v = minangle;
minangle = 360.0;
for(i = M+1; i < N; i++)
if (theta(p[M], p[i]) > v)
if (theta(p[M], p[i]) < minangle)
{ min = i; minangle = theta(p[M], p[min]); }
} while (min < N);
return M;
}
//
// Test above algorithms.
//
main(int argc, char *argv[])
{ struct POINT testarray[] =
{ {3, 9}, // point A, Test set pg. 349
{11, 1},
{6, 8},
{4, 3},
{5, 15},
{8, 11},
{1, 6},
{7, 4},
{9, 7},
{14, 5},
{10, 13},
{16, 14},
{15, 2},
{13, 16},
{3, 12},
{12, 10}, // point P
{0, 0} // scratch space
};
int i,
arraysize,
pointsonhull;
float scalex = 10.0,
scaley = 12.8,
minx,
miny,
maxx,
maxy;
struct videoconfig vconfig;
arraysize = sizeof(testarray)/sizeof(testarray[0])-1;
pointsonhull = wrap(testarray, arraysize);
printf("Points on hull %d\n", pointsonhull);
minx = FLT_MAX;
maxx = FLT_MIN;
miny = FLT_MAX;
minx = FLT_MIN;
for(i = 0; i <= arraysize; i++)
{ printf("Point %2d: %2.1f %2.1f\n", i, testarray[i].x, testarray[i].y);
// compute scaling values for x & y.
minx = min(minx, testarray[i].x);
maxx = max(maxx, testarray[i].x);
miny = min(miny, testarray[i].y);
maxy = max(maxy, testarray[i].y);
}
i = getch();
if (_setvideomode(_MAXRESMODE) == 0)
{ printf("initialize video to max res. failed\n");
exit(1);
}
_getvideoconfig(&vconfig);
scalex = (vconfig.numxpixels*.9) / (maxx - minx);
scaley = (vconfig.numypixels*.9/1.28) / (maxy - miny) * 1.28;
if (vconfig.bitsperpixel>1)
_setcolor(3);
else
_setcolor(1);
for(i = 0; i <= arraysize; i++)
_setpixel((short)(testarray[i].x*scalex), (short)(testarray[i].y*scaley));
i = getch();
if (vconfig.bitsperpixel>1)
_setcolor(2);
_moveto((short)(testarray[0].x*scalex), (short)(testarray[0].y*scaley));
for(i = 1; i <= pointsonhull; i++)
_lineto((short)(testarray[i].x*scalex), (short)(testarray[i].y*scaley));
_lineto((short)(testarray[0].x*scalex), (short)(testarray[0].y*scaley));
i = getch();
_setvideomode(_DEFAULTMODE);
}